package com.example.demo.suanfa_总结;

/**
 *
 * 总结：
 *      归并排序：重点在归并规程，并熟悉归并细节，加以解决问题
 *              merge() 函数
 *              整体-->2分排序两块，递归做
 *              没次步长  i<<1 乘以2 左右 排序
 *              1.小和问题，每个数字左侧比自己小的和
 *              2.数组中，比自己大的数有多少个
 *              3.
 *      荷兰国旗：
 *
 *              1.选点目标数，依次做比较，如果小于等于目标值 小于 区域右扩
 *              2.如果大于目标值，指针直接next
 *              3.如果出现小于的时候，区域与index位置不同，需要替换小于区域index+1的位置替换，小于等于区域右移一位
 *
 *
 *              小于区域 ] 等于区域 [ 大于区域
 *              指针从左向右移动
 *              1.小于 指定值 小于区域右移动，指针也右移
 *              2.等于 指针右移动
 *              3.大于 指定值 与大于区域外 最左的数交换，大于区域左移动，小于区域不动，指针不动
 *
 *      快排：利用荷兰国旗解题部分数据，再利用内层的递归遍历排序 返回的结果！
 *
 *      系统比较器：
 *          return 升序的话：
 *          返回负数的话，认为第一个数排前面   升序
 *          返回正数的话，认为第二个数排前面   降序
 *          返回0的话，无所谓
 *
 *
 *      堆：优先级队列-->完全二叉树（满二叉树，或者在顺序变满的路上）
 *          规律：
 *              父亲index --> 左子位置 = 2*index +1  右子位置 = 2*index+2
 *              子index --> 父亲位置：（index-1）/2
 *      堆--是完全二叉树  大根堆 小根堆
 *          大根堆 maxIndex = 0 index 小根堆 minIndex = 0
 *          insert加入值，加入数组末尾，向上找父亲，进行交换
 *          delete max or min 从0index 交换道数组末尾，在从0  位置向下找位置，大根堆，找大孩子交换
 *          问题：近乎有序的数组，k范围内可排序，小根堆排序即可
 *          问题：最大线段重合问题
 *          问题：
 *
 *          加强堆！！！待看
 *              可以找到某个位置 O1 时间复杂度 找到某个元素 ，使用反向索引，多出功能：contain()
 *              结构：heap[] hashmap heapSize comparator比较器
 *
 *      trie prefix tree 很重要
 *          node  属性: pass 经过次数  end 是否有以这个结尾的字符串 next Node[]
 *
 *
 * 排序算法总结：
 *      计数排序，基于比较的排序，冒泡，插入，选择排序，归并排序，堆排序，希尔排序
 *      不基于比较的（桶排序）     数据情况特殊 ，范围和值特殊
 *
 *      排序算法稳定性
 *
 *
 *      链表
 *          快慢指针 -->是否有环/ 找到中点
 *          题目：奇数个返回中点 ，偶数个 返回上中点，返回下中点
 *              第三题：奇数个，返回中点的上一个中点，偶数个返回上中点的前一个
 *              第四题：奇数个，返回中点前一个 偶数个返回下中点前一个
 *      树形结构
 *          前中后遍历，递归
 *          // 前
 *          process(node.left)
 *          // 中
 *          process(node.right)
 *          // 后
 *          非递归：
 *          难点：非递归 中序遍历，使用栈结构，先左孩子都放入，到底
 *
 *          BFS 和 DFS
 *          先序遍历  和  使用队列的层序遍历
 *
 *          二叉树经典递归套路
 *              1.向子树要所有信息，子树可以提供的那种
 *              2.每个子过程，返回封装好的结果
 *
 *
 *     贪心算法：暂时没看
 *
 *     并查集：
 *          find 和 union 过程
 *          find 找到自己的head ，并压缩路径
 *          union 找到size大一点的，向大的合并
 *
 *          使用矩阵方式/或者使用表的形式 ，使用的成员变量是一致的。
 *         // 自己的父级是
 *         int[] parent;
 *         // 头结点 自身的节点数
 *         int[] headSize;
 *         // 辅助结构
 *         int[] help;
 *         // 内有多少 结构
 *         int sets;
 *
 *
 *
 *
 *
 *
 *
 */




